package tree;

/**
 * 二叉查找树的相关操作
 * 这个二叉树只支持不重复的数据
 */
public class BinTree {

    public static LinkedNode find(int a, LinkedNode pNode) {
        LinkedNode pTemp = pNode;
        while (pTemp != null) {
            int iTemp = (int) pNode.getObjData();
            if (iTemp == a) {
                return pTemp;
            } else if (iTemp < a) {
                pTemp = pTemp.getRightNode();
            } else {
                pTemp = pTemp.getLeftNode();
            }
        }

        return null;
    }

    public static void insert(int a, LinkedNode pNode) {
        if (pNode == null) {
            pNode = new LinkedNode();
            pNode.setObjData(a);
            return;
        }

        LinkedNode pNodeTemp = pNode;
        while (pNodeTemp != null) {
            int iValue = (int) pNodeTemp.getObjData();
            if (a < iValue) {
                if (pNodeTemp.getLeftNode() == null) {
                    LinkedNode pNodeItem = new LinkedNode();
                    pNodeItem.setObjData(a);
                    pNodeTemp.setLeftNode(pNodeItem);
                    return;
                } else {
                    pNodeTemp = pNodeTemp.getLeftNode();
                }
            } else {
                if (pNodeTemp.getRightNode() == null) {
                    LinkedNode pNodeItem = new LinkedNode();
                    pNodeItem.setObjData(a);
                    pNodeTemp.setRightNode(pNodeItem);
                    return;
                } else {
                    pNodeTemp = pNodeTemp.getRightNode();
                }
            }
        }
    }

    public static void delete(int a, LinkedNode pNode) {
        if (pNode == null) {
            return;
        }

        LinkedNode pNodeParent = null;
        LinkedNode pNodeCurrent = pNode;
        while (pNodeCurrent != null && a != (int)pNodeCurrent.getObjData()) {
            pNodeParent = pNodeCurrent;
            int iValue = (int) pNodeCurrent.getObjData();
            if (iValue > a) {
                pNodeCurrent = pNodeCurrent.getLeftNode();
            } else {
                pNodeCurrent = pNodeCurrent.getRightNode();
            }
        }

        //没找到
        if (pNodeCurrent == null) {
            return;
        }

        //被删除的节点有两个子节点, 找到右子树下的最小节点
        if (pNodeCurrent.getRightNode() != null && pNodeCurrent.getLeftNode() != null) {
            LinkedNode pNodeMinParentTemp = pNodeCurrent;
            LinkedNode pNodeMinChildTemp = pNodeCurrent.getRightNode();
            while (pNodeMinChildTemp.getLeftNode() != null) {
                pNodeMinParentTemp = pNodeMinChildTemp;
                pNodeMinChildTemp = pNodeMinChildTemp.getLeftNode();
            }

            pNodeCurrent.setObjData(pNodeMinChildTemp.getObjData());
            pNodeMinParentTemp.setLeftNode(null);

        } else {
            //单个节点需要判断在哪边，同时还存在没有子节点的情况
            LinkedNode pNodeChild = null;
            if (pNodeCurrent.getRightNode() != null) {
                pNodeChild = pNodeCurrent.getRightNode();
            } else if (pNodeCurrent.getLeftNode() != null) {
                pNodeChild = pNodeCurrent.getLeftNode();
            }

            if (pNodeParent == null) {
                pNode = pNodeChild;
            } else if (pNodeParent.getLeftNode() == pNodeCurrent) {
                pNodeParent.setLeftNode(pNodeChild);
            } else if (pNodeParent.getRightNode() == pNodeCurrent){
                pNodeParent.setRightNode(pNodeChild);
            }
        }
    }

}
